//给你一个链表数组，每个链表都已经按升序排列。 
//
// 请你将所有链表合并到一个升序链表中，返回合并后的链表。 
//
// 
//
// 示例 1： 
//
// 输入：lists = [[1,4,5],[1,3,4],[2,6]]
//输出：[1,1,2,3,4,4,5,6]
//解释：链表数组如下：
//[
//  1->4->5,
//  1->3->4,
//  2->6
//]
//将它们合并到一个有序链表中得到。
//1->1->2->3->4->4->5->6
// 
//
// 示例 2： 
//
// 输入：lists = []
//输出：[]
// 
//
// 示例 3： 
//
// 输入：lists = [[]]
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// k == lists.length 
// 0 <= k <= 10^4 
// 0 <= lists[i].length <= 500 
// -10^4 <= lists[i][j] <= 10^4 
// lists[i] 按 升序 排列 
// lists[i].length 的总和不超过 10^4 
// 
//
// Related Topics 链表 分治 堆（优先队列） 归并排序 👍 3052 👎 0


//leetcode submit region begin(Prohibit modification and deletion)



import java.util.PriorityQueue;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
//    public ListNode mergeKLists(ListNode[] lists) {
//        if(lists.length == 0)
//            return null;
//        return mergeKLists(lists, 0, lists.length - 1);
//    }
//    private ListNode mergeKLists(ListNode [] lists, int left, int right){
//        if(left == right)//数组内只有一个链表
//            return lists[left];
//        int m = (left + right)>>> 1;
//        ListNode leftList = mergeKLists(lists, left, m);
//        ListNode rightList = mergeKLists(lists, m + 1, right);
//        return mergeTwoList(leftList, rightList);
//    }
//
//    //合并两个链表
//    private ListNode mergeTwoList(ListNode l1, ListNode l2){
//        ListNode s = new ListNode(-1, null);//哨兵节点
//        ListNode p = s;
//        while(l1!=null && l2!=null){
//            //确定当前的p指针指向
//            if(l1.val < l2.val){
//                p.next = l1;
//                l1 = l1.next;
//            }else{
//                p.next = l2;
//                l2 = l2.next;
//            }
//            p = p.next;//移动指针
//        }
//        p.next = l1==null?l2:l1;
//        return s.next;
//    }
    //豆包，使用小顶堆实现
    public ListNode mergeKLists(ListNode[] lists){
        //边界条件处理
        if(lists == null || lists.length ==0){
            return null;
        }
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a,b)->a.val - b.val);// 小顶堆：值小的节点优先级高
        for(ListNode node : lists){
            if(node != null){
                minHeap.offer(node);
            }
        }
        ListNode s = new ListNode(-1, null);//哨兵节点
        ListNode p = s;
        while(!minHeap.isEmpty()){
            ListNode min = minHeap.poll();
            p.next = min;
            p = p.next;
            if(min.next != null){
                minHeap.offer(min.next);
            }
        }
        return s.next;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
